#include <iostream>
#include <fstream>
#include "SortingConfig.h"

using namespace std;

void swap(int &a, int &b) {
    int t=a;
    a = b;
    b = t;
}

void heap_sort(int *arr, int n) {
    // 堆排序算法
    // 1、构建大顶堆
    int j, p;
    for(int i=1; i<n; ++i) {
        j = i;
        // 当前节点元素与父节点元素比较，如果大于父节点则交换，否则结束
        // 不考虑另外一个兄弟节点的原因是插入的堆已经是大顶堆，父节点必然大于等于子节点
        while(j>0 && arr[(j-1)/2] < arr[j]) {
            swap(arr[j], arr[(j-1)/2]);
            j = (j-1)/2;
        }
    }

    // 2、依次弹出大顶元素，置于数组尾部
    for(int i=n-1; i>0; --i) {
        // 将当前最大元素与未排序数组尾部交换
        swap(arr[0], arr[i]);
        // 交换后的堆长度减1，并重新构建大顶堆
        j = 0;
        while(2*j+1 < i) {
            p = 2*j+1;
            if (p+1 < i && arr[p+1] > arr[p]) p++;
            if (arr[j] < arr[p]) {
                swap(arr[j], arr[p]);
                j = p;
            } else break;  // 不需要调整时结束
        }
    }
}

int main(int argc, char *argv[]) {
    cout << "Sorting Version: " << Sorting_VERSION_MAJOR 
         << "." << Sorting_VERSION_MINOR<<endl;
    // 参数解析
    ifstream input;
    if (argc > 1) {
        input.open(argv[1], ios::in);
    }

    int n;
    if (argc > 1) input >> n;
    else cin >> n;
    int arr[n];
    if (argc > 1){
        for(int i=0; i<n;++i) input >> arr[i];
        input.close();
    } else {
        for(int i=0; i<n;++i) cin >> arr[i];
    }
    // 排序
    heap_sort(arr, n);

    for(int i=0; i<n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}